/*
 * @lc app=leetcode.cn id=107 lang=javascript
 *
 * [107] 二叉树的层次遍历 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function (root) {
  // BFS，按层存储结果
  const getResult = (root, result) => {
    const queue = [root];
    while (queue.length) {
      let size = queue.length;
      result.push([]);
      while (--size >= 0) {
        let node = queue.shift();
        result[result.length - 1].push(node.val);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
      }
    }
  };
  // 翻转结果
  const reverse = (result) => {
    for (let i = 0, j = result.length - 1; i < j; i++, j--) {
      [result[i], result[j]] = [result[j], result[i]];
    }
  };

  const result = [];

  if (root === null) return result;

  getResult(root, result);
  reverse(result);
  return result;
};
// @lc code=end
